package com.demo.alg.chapter15动态规划.矩阵取数问题;

import java.util.ArrayList;
import java.util.List;

/**一个N*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。例如：3 * 3的方格。

1 3 3
2 1 3
2 2 1

能够获得的最大价值为：11。
 * @author zhangsulei
 *
 */
public class Dp03 {

	public static void main(String[] args) {
		int[] arr = new int[]{1, 3, 3, 2, 5, 3, 2, 2, 1};
		int index = 0;
        int n = 3;
        int[] dp = new int[n+1];
        Trace[] traces = new Trace[n+1];
        for (int i = 0; i < traces.length; i++) {
        	traces[i] = new Trace();
		}
        int[] readMax = new int[n+1];

        for(int i=0; i<n; i++){
            for(int k=1; k<n+1; k++){
                readMax[k] = arr[index++];
            }
            for(int j=1; j<n+1; j++){
            	if(dp[j-1] > dp[j]){
            		traces[j].traceList.clear();
            		traces[j].traceList.addAll(traces[j-1].traceList);
            	}
            	traces[j].traceList.add(new Position(i, j));
                dp[j] = Math.max(dp[j], dp[j-1]) + readMax[j];
            }
        }

        String s = "";
        List<Position> traceList = traces[n].traceList;
        for (Position p : traceList) {
        	s = s + arr[p.rowIndex * 3 + (p.columnIndex - 1)] + "+";
		}
        System.out.println(s.substring(0, s.length()-1) + "=" +dp[n]);
    }

	static class Trace{
		List<Position> traceList = new ArrayList<>();

		@Override
		public String toString() {
			return "Trace [traceList=" + traceList + "]";
		}
	}

	static class Position{
		public int rowIndex = 0;
		public int columnIndex = 0;
		public Position(int rowIndex, int columnIndex) {
			super();
			this.rowIndex = rowIndex;
			this.columnIndex = columnIndex;
		}
		@Override
		public String toString() {
			return "(" + rowIndex + ", " + columnIndex + ")";
		}
	}

}
